//
//  STLUsage.cpp
//  CppDemo
//
//  Created by 蒋益杰 on 16/5/19.
//  Copyright © 2016年 com.ed. All rights reserved.
//

#include "STLUsage.hpp"
#include <iostream>
#include <unordered_map>
#include <queue>

using namespace std;

void STLUsage::print(const std::string& s)
{
    cout << s << endl;
}

vector<int> STLUsage::topKFrequent(vector<int>& nums, int k)
{
    vector<int> result;
    unordered_map<int, int> mapping;
    for (int num: nums) {
        mapping[num]++;
    }
    
    priority_queue<pair<int, int>> pri_queue;
    for (auto it = mapping.begin(); it != mapping.end(); it++) {
        pri_queue.push(make_pair(it->second, it->first));
    }
    
    while (result.size() < k) {
        result.push_back(pri_queue.top().second);
        pri_queue.pop();
    }
    
    return result;
}


ListNode* partition(ListNode* head, int x)
{
    if (head == NULL) {
        return head;
    }
    ListNode *less = new ListNode(0), *less_tail = less;
    ListNode *greater = new ListNode(0), *greater_tail = greater;
    ListNode *cur = head;
    
    while (cur) {
        if (cur->val < x) {
            less_tail->next = cur;
            cur = cur->next;
            less_tail = less_tail->next;
            less_tail->next = NULL;
        }
        else
        {
            greater_tail->next = cur;
            cur = cur->next;
            greater_tail = greater_tail->next;
            greater_tail->next = NULL;
        }
    }
    
    less_tail->next = greater->next;
    return less->next;
}

TreeNode* constructCore(vector<int>& inorder, size_t inBegin, size_t inEnd,
                               vector<int>& postorder, size_t postBegin, size_t postEnd)
{
    if (inBegin > inEnd) {
        return NULL;
    }
    int rootValue = postorder[postEnd];
    TreeNode *root = new TreeNode(rootValue);
    root->left = root->right = NULL;
    
    if (inBegin == inEnd) {
        if (postBegin == postEnd) {
            return root;
        }
    }
    
    size_t index;
    for (size_t i = inBegin; i <= inEnd; i++) {
        if (rootValue == inorder[i]) {
            index = i;
            break;
        }
    }
    
    size_t len = index - inBegin;
    root->left = constructCore(inorder, inBegin, index - 1, postorder, postBegin, postBegin + len - 1);
    root->right = constructCore(inorder, index + 1, inEnd, postorder, postBegin + len, postEnd - 1);
    
    return root;
}

TreeNode *createTree(vector<int> &inorder, size_t inBeg, size_t inEnd, vector<int> &postorder, size_t postBeg, size_t postEnd)
{
    if (inBeg > inEnd)
        return NULL;
    
    size_t root = postorder[postEnd];
    
    size_t index;
    
    for(size_t i = inBeg; i <= inEnd; i++)
        if (inorder[i] == root)
        {
            index = i;
            break;
        }
    
    size_t len = index - inBeg;
    TreeNode *left = createTree(inorder, inBeg, index - 1, postorder, postBeg, postBeg + len - 1);
    TreeNode *right = createTree(inorder, index + 1, inEnd, postorder, postBeg + len, postEnd - 1);
    
    TreeNode *node = new TreeNode(root);
    node->left = left;
    node->right = right;
    
    return node;
}

TreeNode* STLUsage::buildTree(vector<int>& inorder, vector<int>& postorder)
{
    if (inorder.empty() || postorder.empty()) {
        return NULL;
    }
    
    return createTree(inorder, 0, inorder.size() - 1, postorder, 0, postorder.size() - 1);
}

#pragma mark - strToInt
long long strToIntCore(const char *digit, bool minus) {
    long long result = 0;
    while (*digit != '\0') {
        if (*digit >= '0' && *digit <= '9') {
            int flag = minus ? -1 : 1;
            result = result * 10 + flag * (*digit - '0');
            
            //判断移除
            if ((!minus && result > 0x7fffffff) ||
                (minus && result < (signed int)0x80000000)) {
                result = 0;
                break;
            }
            digit++;
        } else {
            result = 0;
            break;
        }
    }
    
    if (*digit == '\0') {
//        g_status______ = kValid;
    }
    return result;
}

int strToInt(const char *str) {
//    g_status______ = kInvalid;
    long long number = 0;
    
    if (str != NULL && *str != '\0') {
        bool minus = false;
        if (*str == '+') {
            str++;
        } else if (*str == '-') {
            minus = true;
            str++;
        }
        
        if (*str != '\0') {
            number = strToIntCore(str, minus);
        }
    }
    return (int)number;
}

int findNumAppearOnce(int data[], int length) {
    if (data == NULL || length < 1) {
        return -1;
    }
    
    int resultExclusiveOR = 0;
    for (int i = 0; i < length; ++i) {
        resultExclusiveOR ^= data[i];
    }
    
    int resultIndex = -1;
    for (int j = 0; j < length; ++j) {
        if (data[j] == resultExclusiveOR) {
            resultIndex = j;
            break;
        }
    }
    return resultIndex;
}

int findNumAppearOnce1(int data[], int length) {
    int bits[32];
    memset(bits, 0, 32 * sizeof(int));
    
    int j = 0;
    for (int i = 0; i < length; ++i) {
        for (j = 0; j < 32; ++j) {
            int k = (data[i] >> j) & 0x1;
            bits[j] += k;
        }
    }
    
    int res = 0;
    for (j = 0; j < 32; ++j) {
        if (bits[j] % 3 != 0) {
            res += (1 << j);
        }
    }
    return res;
}

#pragma mark - 6
int getFirstK(int *data, int length, int k, int start, int end) {
    if (start > end) {
        return -1;
    }
    
    int mid = (start + end) >> 1;
    int midVal = data[mid];
    
    if (midVal == k) {
        if ((mid > 0 && data[mid - 1] != k)
            || mid == 0) {
            return mid;
        } else {
            return -1;
        }
    } else if (midVal > k) {
        end = mid - 1;
    } else {
        start = mid + 1;
    }
    
    return getFirstK(data, length, k, start, end);
}

int getLastK(int *data, int length, int k, int start, int end) {
    if (start > end) {
        return -1;
    }
    
    int mid = (start + end) >> 1;
    int midVal = data[mid];
    
    if (midVal == k) {
        if ((mid < length - 1 && data[mid + 1] != k)
            || mid == length - 1) {
            return mid;
        } else {
            return -1;
        }
    } else if (midVal < k) {
        start = mid + 1;
    } else {
        end = mid - 1;
    }
    return getLastK(data, length, k, start, end);
}

int getNumberOfK(int *data, int length, int k) {
    int number = 0;
    
    if (data != NULL && length > 0) {
        int start = getFirstK(data, length, k, 0, length - 1);
        int end = getLastK(data, length, k, 0, length - 1);
        
        if (start > -1 && end > -1) {
            number = end - start + 1;
        }
    }
    return number;
}

#pragma mark - tree
int treeDepth(TreeNode *pRoot) {
    if (!pRoot) {
        return 0;
    }
    
    int nLeft = treeDepth(pRoot->left);
    int nRight = treeDepth(pRoot->right);
    
    return (nLeft > nRight) ? (nLeft + 1) : (nRight + 1);
}

int nMaxLen1 = 0;

void findMaxLen(NODE *pRoot) {
    if (!pRoot) {
        return;
    }
    
    if (!pRoot->pLeft) {
        pRoot->nMaxLeft = 0;
    }
    if (!pRoot->pRight) {
        pRoot->nMaxRight = 0;
    }
    
    if (pRoot->pLeft) {
        findMaxLen(pRoot->pLeft);
    }
    if (pRoot->pRight) {
        findMaxLen(pRoot->pRight);
    }
    
    if (pRoot->pLeft) {
        int nTempMax = 0;
        if (pRoot->pLeft->nMaxLeft > pRoot->pLeft->nMaxRight) {
            nTempMax = pRoot->pLeft->nMaxLeft;
        } else {
            nTempMax = pRoot->pLeft->nMaxRight;
        }
        pRoot->nMaxLeft = 1 + nTempMax;
    }
    
    if (pRoot->pRight) {
        int nTempMax = 0;
        if (pRoot->pRight->nMaxLeft > pRoot->pRight->nMaxRight) {
            nTempMax = pRoot->pRight->nMaxLeft;
        } else {
            nTempMax = pRoot->pRight->nMaxRight;
        }
        pRoot->nMaxRight = 1 + nTempMax;
    }
    
    if (pRoot->nMaxLeft + pRoot->nMaxRight > nMaxLen1) {
        nMaxLen1 = pRoot->nMaxLeft + pRoot->nMaxRight;
    }
}

TreeNode *insert(TreeNode *root, int val) {
    TreeNode *node = new TreeNode(val);
    if (!root) {
        root = node;
        return root;
    }
    
    TreeNode *p = root;
    while (p != NULL) {
        if (p->val > val) {
            if (p->left == NULL) {
                p->left = node;
                return root;
            }
            p = p->left;
        } else {
            if (p->right == NULL) {
                p->right = node;
                return root;
            }
            p = p->right;
        }
    }
    return root;
}

